package com.erbao.datastructurearithmetic.tyro;

/**
 * @author CaoBaoYin
 * @since 21/7/28 10:46
 */
public class Class3 {

    public static void main(String[] args) {
        // 验证算法
        int maxLen = 100;
        int maxVal = 100;
        int testTimes = 10000000;
        for (int i = 0; i < testTimes; i++) {
            int[] arr = adjacentNotEqualsRandomArr(maxLen, maxVal);

            int index = oneMinIndex(arr);
            if (!checkOneMinIndex(arr, index)) {
                System.out.println("出错了！");
                System.out.println(index);
                Class1.show(arr);
                break;
            }
        }
        System.out.println("nice");
    }

    private static int oneMinIndex(int[] arr){
        if (arr==null || arr.length==0) return -1;

        int n = arr.length;
        if (n == 1) return 0;

        if (arr[0]<arr[1]) return 0;
        if (arr[n-2]>arr[n-1]) return n-1;

        int l = 0, r=n-1, res=-1;
        while (l <= r) {
            int mid = (l+r) >>> 1;

            // mid == l == 0此时必定r=1 且 arr[0]>arr[1] r左移的条件是arr[mid] < arr[mid+1]则a[1]<a[2]
            if (mid-1 < 0) {
                res = 1;
                break;
            }

            if (arr[mid]<arr[mid-1] && arr[mid] < arr[mid+1]) {
                res = mid;
                break;
            }

            /*剩下三种情况
            * arr[mid]>arr[mid+1] arr[mid]>arr[mid-1]
            * arr[mid]>arr[mid+1] arr[mid]<arr[mid-1]
            * arr[mid]<arr[mid+1] arr[mid]>arr[mid-1]*/
            if (arr[mid] < arr[mid+1]) {
                r = mid - 1;
            } else {
                l = mid + 1;
            }
        }
        return res;
    }

    /**
     * 验证局部最小的角标是不是对的
     */
    private static boolean checkOneMinIndex (int[] arr, int index){
        if (arr == null || arr.length == 0) return index == -1;

        int n = arr.length;
        if (n == 1) return index == 0;

        if (index == 0) return arr[0] < arr[1];

        if (index == n-1) return arr[n-1] < arr[n-2];

        return arr[index] < arr[index+1] && arr[index]<arr[index-1];
    }

    /**
     * 产生相邻不等的数据
     */
    public static int[]  adjacentNotEqualsRandomArr(int maxLen, int maxValue){
        int len = (int)(Math.random()*maxLen);
        if (len == 0) return null;

        int[] arr = new int[len];
        arr[0] = (int)(Math.random()*maxValue);
        for (int i = 1; i < len; i++) {
            do {
                arr[i] = (int)(Math.random()*maxValue);
            } while (arr[i] == arr[i-1]);
        }
        return arr;
    }

    /**
     * 二分查找数组中最左位置
     * @param arr 升序数组
     * @param num 要查找的数
     * @return 位置角标
     */
    private static int binarySearchMostLeft(int[] arr, int num){
        if (arr == null || arr.length==0) return -1;

        int res = -1;
        int l = 0;
        int r = arr.length-1;
        while (l <= r) {
            int mid = (l+r) >>> 1;
            int midVal = arr[mid];

            if (midVal < num) {
                l = mid + 1;
            } else {
                res = mid;
                r = mid - 1;
            }
        }
        return res;
    }

    /**
     * 遍历查找数组中最左位置
     */
    private static int traversalSearchMostLeft(int[] arr, int num){
        if (arr == null || arr.length==0) return -1;

        int n = arr.length;
        for (int i = 0; i < n; i++) {
            if (arr[i] >= num) {
                return i;
            }
        }
        return -1;
    }

    /**
     * 有序数组二分查找
     */
    private static boolean binarySearch (int[] arr, int num) {
        if (arr == null || arr.length==0) return false;

        int l = 0, r = arr.length-1;
        while (l <= r) {
            int mid = (l+r) >>> 1;
            int midVal = arr[mid];

            if (midVal < num) {
                l = mid + 1;
            } else if (midVal > num) {
                r = mid - 1;
            } else {
                return true;
            }
        }

        return false;
    }

    /**
     * 遍历查找
     */
    private static boolean traversalSearch (int[] arr, int num) {
        if (arr == null || arr.length==0) return false;

        int n = arr.length;
        for (int value : arr) {
            if (value == num) {
                return true;
            }
        }
        return false;
    }



}
